package com.zdj;

import java.util.Arrays;

/**
 * @author zhangdj
 * @date 2021-10-06 14:59:53
 * 归并排序
 * 核心：将两个排好序的数组进行合并
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr1 = {1, 5, 3, 8, 9, 34, 21, 7, -2};
        System.out.println(Arrays.toString(mergeSort(arr1)));
    }

    private static int[] mergeSort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int mid = arr.length / 2;
        // 拆分数组
        int[] arr1 = Arrays.copyOfRange(arr, 0, mid);
        int[] arr2 = Arrays.copyOfRange(arr, mid, arr.length);
        // 递归拆分
        return merge(mergeSort(arr1), mergeSort(arr2));
    }

    /**
     * 合并两个有序数组
     *
     * @param arr1 数组1
     * @param arr2 数组2
     * @return 合并后的数组
     */
    private static int[] merge(int[] arr1, int[] arr2) {
        if (arr1 == null && arr2 == null) {
            return new int[]{};
        }
        if (arr1 == null) {
            return arr2;
        }
        if (arr2 == null) {
            return arr1;
        }
        int[] temp = new int[arr1.length + arr2.length];
        // 数组1的索引
        int i = 0;
        // 数组2的索引
        int j = 0;
        // temp的索引
        int k = 0;
        while (i < arr1.length && j < arr2.length) {
            // 较小的元素放到temp，索引加1
            if (arr1[i] >= arr2[j]) {
                temp[k++] = arr2[j++];
            } else {
                temp[k++] = arr1[i++];
            }
        }
        while (i < arr1.length || j < arr2.length) {
            // 当一个数组为空时，将另一个数组的所有元素加到temp
            if (i >= arr1.length) {
                temp[k++] = arr2[j++];
            }
            if (i < arr1.length) {
                temp[k++] = arr1[i++];
            }
        }
        return temp;
    }
}
